package Graph.graphWithWeight.MinistedTree.Prim;

import Graph.graphWithWeight.EdgeWeight;
import Graph.graphWithWeight.GraphWeight;
import Graph.graphWithWeight.MinistedTree.Kruskal.ConnectComponent;

import java.util.ArrayList;

/**
 * @Author: 蔡翔
 * @Date: 2020/3/1 9:25
 * @Version 1.0
 * prim 算法就是要从一个顶点触发 ，由一个顶点向外蔓延。
 * 核心掌握切分定理
 */
public class Prim {
    private GraphWeight G;
    private ArrayList<EdgeWeight> mst;

    public Prim(GraphWeight G){
        this.G = G;
        mst = new ArrayList<>();
        ConnectComponent cc = new ConnectComponent(G);
        if(cc.count()>1){return;}
        //prim
        //切分开始 分成 1 和 v-1 部分，用bool表示切分，，用visited[] 模拟切分
        boolean[] visited = new boolean[G.V()];
        visited[0] = true;

        //因为所有节点已经被分为 1，v-1 了所以最外层for循环只要 循环 n-1次就行了
        for(int i=1;i<G.V();i++){
            EdgeWeight minst = new EdgeWeight(-1,-1,Integer.MAX_VALUE);
            //这里就是算法最巧妙的地方，某个节点已经找好最小边了，那么这个节点就就和之前的节点融为一体了，那么在之后的遍历中，是看这个整体 中找最小边的
            //所以在i=2 的时候有下面的算法
            for(int v=0;v<G.V();v++){
                //如果visited为true 那么说明是一类切分（是1的那类，而不是v-1那类）
                if(visited[v]){
                    for(int w:G.adj(v)){
                        //!visited[w] 代表的是 边的另外一个节点，并没有融入我的本体。
                        if(!visited[w] && G.getWeight(v,w)<minst.getWeight()){
                            minst = new EdgeWeight(v,w,G.getWeight(v,w));
                        }
                    }
                }
            }
            mst.add(minst);
            visited[minst.getV()] = true;
            visited[minst.getW()] = true;
        }

    }

    public ArrayList<EdgeWeight> result(){
        return mst;
    }

    public static void main(String[] args) {
        GraphWeight g = new GraphWeight("gPrim.txt");
        Prim prim = new Prim(g);
        System.out.println(prim.result());
    }
}
